package demo.practice.sort;

public class Ms1714 {
    public static void main(String[] args) {
        Ms1714 ms1714= new Ms1714();
        ms1714.smallestK(new int[]{4,6,2,3,9},3);
    }
    public int[] smallestK(int[] arr, int k) {
        int[] res = new int[k];
        quickSort(arr,0,arr.length-1,k);
        for (int i = 0; i < res.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public void quickSort(int[] arr, int l, int r, int k) {

        int pos = partition(arr, l, r);
        if (pos == k-1) {
            return;
        }else if(pos> k-1){
            //pos在右边，
            quickSort(arr,l,pos-1,k);
        }else {
            quickSort(arr,pos+1,r,k);
        }
    }

    public int partition(int[] arr, int l, int r) {
        int point = arr[l];
        int[] cp = new int[r - l + 1];
        int i = l + 1;
        int min = 0, max = cp.length - 1;
        for (; i <= r; i++) {
            if (arr[i] >= point) {
                cp[max--] = arr[i];
            } else {
                cp[min++] = arr[i];
            }
        }
        cp[min] = point;
        System.arraycopy(cp, 0, arr, l, r - l + 1);
        return min + l;
    }


}
